We study a sorted list, a data structure containing records {Ri}, each uniquely identified by a key {k(Ri)} which supports the operations Search (
,k), Insert(
,k) and Delete(
,k) to search, insert and delete a record R with key k. For the efficiency of Search(
,k), records are stored with their keys in sorted order. Insertion then generally requires shifting entries in the structure to make room for the record to be inserted. To improve the efficiency of Insert(
,k), records are stored in a circular buffer with ''gaps" which is expanded and contracted during a sequence of insertions and deletions depending upon the current number of keys in
. We assess in this paper the amount of work required to insert a sequence of records.
By: Alon Itai, Alan G. Konheim, Michael Rodeh
Published in: RC9146 in 1981
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .